package day23;

import java.util.Arrays;

/**
 * 给定整数 n ，返回 所有小于非负整数n的质数的数量 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：n = 10
 * 输出：4
 * 解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
 * 示例 2：
 *
 * 输入：n = 0
 * 输出：0
 * 示例 3：
 *
 * 输入：n = 1
 * 输出：0
 *
 *
 */
public class Solution11 {
    public int countPrimes(int n) {
        boolean []isPrime = new boolean[n];
        Arrays.fill(isPrime,true);
        int ans = 0;
        for (int i = 2; i < n; i++) {
            if(isPrime[i]){
                ans++;
                if ((long)i*i<n) {
                    for (int j = i*i; j < n; j+=i) {
                        isPrime[j]=false;
                    }
                }
            }
        }
        return ans;
    }
}
